#include "common.h"

int ans;
int n, m;
int sum;
int arr[20][20];
int arr1[4][2] = { {1,0}, {-1,0}, {0,1},{0,-1} };

void dfs(vector<vector<int>>& grid, int x, int y, int num)
{
	if (grid[x][y] == 2)
	{
		if (num == sum)
		{
			ans++;
		}
		return;
	}
	for (int i = 0; i < 4; i++)
	{
		int xx = x + arr1[i][0];
		int yy = y + arr1[i][1];
		if (xx >= 0 && xx < n && yy >= 0 && yy < m)
		{
			if (arr[xx][yy] == 0)
			{
				arr[xx][yy] = 1;
				dfs(grid, xx, yy, num + 1);
				arr[xx][yy] = 0;
			}
		}
	}
}

int uniquePathsIII(vector<vector<int>>& grid)
{
	n = grid.size();
	m = grid[0].size();
	sum = n * m;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (grid[i][j] == -1)
			{
				arr[i][j] = 1;
				sum--;
			}
		}
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (grid[i][j] == 1)
			{
				arr[i][j] = 1;
				dfs(grid, i, j, 1);
				break;
			}
		}
	}
	return ans;
}